package structures.sort;

import java.util.Arrays;

public class ShellSortDemo {

    private static final int LENGTH = 80000;

    public static void main(String[] args) {
        // 生成数据
        int[] data = new int[LENGTH];
        for (int index = 0; index < data.length; index++) {
            data[index] = (int) (Math.random() * LENGTH);
        }

        // 打印数据
        System.out.println(Arrays.toString(data));

        long startTime = System.currentTimeMillis();
        shellSort(data);
        System.out.println("----------------消耗时间: " + (System.currentTimeMillis() - startTime) + " ms------------");

        // 打印数据
        System.out.println(Arrays.toString(data));
    }


    // 希尔排序   设置不同的步长分组 遍历  组内比较(插入排序)
    public static void shellSort(int[] data) {
        for (int gap = data.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < data.length; i++) {
                // 遍历各组中的元素  这里运用插入排序的思想 break是点睛之笔
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (data[j] > data[j + gap]) {
                        int temp = data[j];
                        data[j] = data[j + gap];
                        data[j + gap] = temp;
                    } else {
                        break;
                    }
                }
            }
        }
    }
}
